#include <binarytree/btree.h>
#include <stdarg.h>
#include <stdlib.h>
#include <assert.h>

static void do_preorder_visit_r(BTreeNode *node, tree_visitor visitor) {
    if (NULL == node) {
        return;
    }
    // 访问节点
    visitor(node);
    // 访问左子树
    do_preorder_visit_r(node->left, visitor);
    // 访问右子树
    do_preorder_visit_r(node->right, visitor);
}

static void do_inorder_visit_r(BTreeNode *node, tree_visitor visitor) {
    if (NULL == node) {
        return;
    }
    // 访问左子树
    do_inorder_visit_r(node->left, visitor);
    // 访问节点
    visitor(node);
    // 访问右子树
    do_inorder_visit_r(node->right, visitor);
}

static void do_postorder_visit_r(BTreeNode *node, tree_visitor visitor) {
    if (NULL == node) {
        return;
    }
    // 访问左子树
    do_postorder_visit_r(node->left, visitor);
    // 访问右子树
    do_postorder_visit_r(node->right, visitor);
    // 访问节点
    visitor(node);
}

static int do_tree_height(BTreeNode *node) {
    if (NULL == node) {
        return 0;
    }
    if (NULL == node->left && NULL == node->right) {
        return 1;
    }
    int h_left = do_tree_height(node->left);
    int h_right = do_tree_height(node->right);
    return h_left >= h_right ? h_left + 1 : h_right + 1;
}

BTree *new_tree() {
    BTree *bt = (BTree*)malloc(sizeof(BTree));
    bt->root = NULL;
    return bt;
}

BTreeNode *new_node(int val) {
    BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode));
    node->data = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

BTreeNode *add_left_child(BTreeNode *node, int val) {
    BTreeNode *left = new_node(val);
    node->left = left;
    return left;
}

BTreeNode *add_right_child(BTreeNode *node, int val) {
    BTreeNode *right = new_node(val);
    node->right = right;
    return right;
}

void preorder_visit_r(BTree *btree, tree_visitor visitor) {
    assert(btree != NULL);
    do_preorder_visit_r(btree->root, visitor);
}

void inorder_visit_r(BTree *btree, tree_visitor visitor) {
    assert(btree != NULL);
    do_inorder_visit_r(btree->root, visitor);
}

void postorder_visit_r(BTree *btree, tree_visitor visitor) {
    assert(btree != NULL);
    do_postorder_visit_r(btree->root, visitor);
}

void preorder_visit(BTree *btree, tree_visitor visitor) {
    assert(btree != NULL && btree->root != NULL);
    // 堆栈
    BTreeNode *stack[100] = {};
    int stack_top = -1;

    // 从根节点开始，边访问边入栈
    BTreeNode *node = btree->root;
    while (node) {
        visitor(node);
        stack_top++;
        stack[stack_top] = node;
        node = node->left;
    }
    // 开始弹栈，直到栈空为止
    while (stack_top >= 0) {
        BTreeNode *top = stack[stack_top];
        stack_top--;
        if (top->right != NULL) {
            visitor(top->right);
            stack_top++;
            stack[stack_top] = top->right;
            // 把左子树全部入栈
            node = top->right->left;
            while (node) {
                visitor(node);
                stack_top++;
                stack[stack_top] = node;
                node = node->left;
            }
        }
    }
}

void level_visit(BTree *btree, tree_visitor visitor) {
    // 队列
    BTreeNode *queue[100] = {0};
    int head = -1, tail = -1;
    // 先将对头入队
    head = 0;
    tail = 0;
    queue[tail] = btree->root;
    while( head <= tail) {
        //出队列
        BTreeNode *head_node = queue[head];
        head++;
        if (head_node != NULL) {
            visitor(head_node);
            // 左右子树入队
            if (head_node->left != NULL) {
                tail++;
                queue[tail] = head_node->left;
            }
            if (head_node->right != NULL) {
                tail++;
                queue[tail] = head_node->right;
            }
        }
    }
}

int tree_height(BTree *btree) {
    assert(btree != NULL);
    return do_tree_height(btree->root);
}

